/**
 * @file   LinkedList.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Thu Oct 29 22:15:23 2020
 * 
 * @brief  Here are the declare and the definition of class LinkedList and its functions
 * 
 * 
 */

#include "Node.h"

template <typename T>
class LinkedList {
private:
    Node<T> * head;
public:
    LinkedList() { head = NULL; };
    void append(T _val);
//    void append(const Node& _add);
    void print() const;
    Node<T> * find(T _val); // return the last address
    void insert(T _val); // insert node
    void del(Node<T> * _add);  // delete the next address    
    ~LinkedList();
};

template <typename T>
void LinkedList<T>::insert(T _val) {
    Node<T> * index = head;
    // create new node
    Node<T> * p = new Node<T>;
    p->set_data(_val);
    // if the LinkedList is empty, set the head with the _val
    if (index==NULL) {
	p->set_next(NULL);
	head = p;
    } else {      
	// if the head's data is larger, let p become the head
	if (index->get_data()>_val) {
	    p->set_next(index);
	    head = p;
	    return;
	}

	// move index to the end of the list or the position before the first data larger than _val
	while (index->get_next()!=NULL && index->get_next()->get_data()<=_val) {
	    index = index->get_next();
	}	

	// if index is the end of the list add p as the last node
	if (index->get_next()==NULL) {
	    index->set_next(p);
	    p->set_next(NULL);
	} else {
	    // if index is the position before the first data larger than _val, insert p between them
	    p->set_next(index->get_next());
	    index->set_next(p);
	}
    }
}

template <typename T>
void LinkedList<T>::del(Node<T> * _add) {
    Node<T> * index = head;
    // if index is not the right address, move it
    while (index!=_add && index!=NULL) {
	index = index->get_next();	
    }
    // if right, link the nodes before and next to it, change its value and delete it
    if (index!=NULL && index->get_next()!=NULL) {
	Node<T> * d = index->get_next();
	Node<T> * tmp = d->get_next();
	index->set_next(tmp);
        d->set_next(NULL);
	delete d;
	d = NULL;
    }
}

template <typename T>
Node<T> * LinkedList<T>::find(T _val) {
    // mark the index and the last index
    Node<T> * index = head;
    Node<T> * last = index;
    int n = 0; // mark the length we find
    while (1) {
	// if it's the end, return NULL
	if (index==NULL) {
	    std::cout << "Not found." << std::endl;
	    return NULL;
	}
	// else continue
	n++;
	T val = index->get_data();
	// if there is only one node, and it is what we need, return NULL
	if (val==_val && n==1) {
	    std::cout << "There is only one data, it fits the condition but nothing to return." << std::endl;
	    return NULL;
	} else if (val==_val){
	    // we find it, return the last address
	    return last;
	}
	// move to the next
	last = index;
	index = index->get_next();
    }
}

template <typename T>
LinkedList<T>::~LinkedList() {
    if (head!=NULL) {
	Node<T> * p = head;
    
	while (p!=NULL) {
	    Node<T> * t = p;
	    p = p->get_next();
	    delete t;
	    t = NULL;
	}

	delete p;
	p = NULL;
    }    
}

template <typename T>
void LinkedList<T>::print() const {
    Node<T> * p = head;

    std::cout << "[";    
    while (p!=NULL) {
	std::cout << p->get_data() << ", ";
	p = p->get_next();
    }
    std::cout << "\b\b" << "]" << std::endl;
}

template <typename T>
void LinkedList<T>::append(T _val) {
    Node<T> * tail  = head;
    Node<T> * p = new Node<T>;
    p->set_data(_val);
    p->set_next(NULL);
    
    if (tail==NULL) {
	head = p;
    } else {
	while (tail->get_next()!=NULL) {
	    tail = tail->get_next();
	}
	tail->set_next(p);
    }
}
